package com.problem.stack;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/binary-tree-preorder-traversal/
 */
public class PreorderTraversal {

    //给定一个二叉树，返回它的 前序 遍历。
    //
    // 示例:
    //
    //输入: [1,null,2,3]
    //   1
    //    \
    //     2
    //    /
    //   3
    //
    //输出: [1,2,3]


    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root,res);
        return res;
    }


    private void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            res.add(root.val);
            TreeNode l = root.left;
            if (l!= null) {
                helper(root.left,res);
            }
            TreeNode r = root.right;
            if (r != null) {
                helper(root.right,res);
            }
        }


    }


    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
